package algorithm.backtracking.leetcode;

import java.util.*;

/**
 * 回溯法解决排列问题
 * @author yuisama
 * @date 2021/12/27 13:16
 **/
public class Num46 {
    private List<List<Integer>> ret = new LinkedList<>();
    // 判断当前数字是否已经使用过，防止重复结果集
    private boolean used[];
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> tempRet = new LinkedList<>();
        used = new boolean[nums.length];
        permuteHelper(nums,0,tempRet);
        return ret;
    }

    /**
     * 向已有结果集tempRet中添加index + 1个元素，获取有index + 1个元素的全排列
     * @param nums
     * @param index
     * @param tempRet 已经存储的nums[i]个结果集
     */
    private void permuteHelper(int[] nums, int index, List<Integer> tempRet) {
        if (index == nums.length) {
            // 此时走完叶子结点，存储一个全排列组合
            // Java的引用！！，此处不能直接使用tempRet，否则在下面删除尾部元素时会同步修改最终结果集的元素
            // 因为指向的是相同的地址!
            // 每次添加都新建一个List，保存当前的结果集
            ret.add(new LinkedList<>(tempRet));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 当前i对应的数字还没被使用，将其加入temp并状态改为true
                tempRet.add(nums[i]);
                used[i] = true;
//                System.out.println("递归前tempRet: " + tempRet + ",index = " + index);
                // 继续向下搜索其余结果集
                permuteHelper(nums,index + 1,tempRet);
                // 走完一个叶子结点后，还原其状态以及剪枝操作(当前走完的叶子节点)
                // 注意删除tempRet的尾元素而不是nums[i]
                // 要删除的是上次递归结束的最后元素，不等于当前的nums[i]
                tempRet.remove(tempRet.size() - 1);
                used[i] = false;
//                System.out.println("递归后tempRet: " + tempRet + ",index = " + index);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2};
        List<List<Integer>> permute = new Num46().permute(nums);
        System.out.println(permute);
    }
}